package ch04.min_gengerate_tree;

import ch04.Edge;
import ch04.EdgeWeightGraph;
import ch04.UF;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class KruskalMST {
    private Queue<Edge> mst;

    public KruskalMST(EdgeWeightGraph graph) {
        mst = new LinkedList<>();
        int v = graph.getV();
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
        UF uf = new UF(v);
        for (Edge edge : graph.edges()) {
            priorityQueue.add(edge);
        }
        while (!priorityQueue.isEmpty() && mst.size() < v - 1) {
            Edge edgePo = priorityQueue.poll();
            int vv = edgePo.either();
            int ww = edgePo.other(vv);
            if (uf.connected(vv, ww)) {
                continue;
            }
            uf.union(vv, ww);
            mst.add(edgePo);

        }
    }

    public Queue<Edge> getMst() {
        return mst;
    }

    public static void main(String[] args) {
        KruskalMST kruskalMST = new KruskalMST(EdgeWeightGraph.getGraph());
        for (Edge edge : kruskalMST.getMst()) {
            System.out.println(edge);
        }
    }


}
